package sort;

/**
 * 堆排序
 *
 * @param <T>
 * @author zj
 */
public class HeapSort<T extends Comparable<T>> implements Sort<T> {

    @Override
    public void sort(T[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        //先初始化堆
        for (int i = (arr.length >>> 1) - 1; i >= 0; i--) {
            siftDown2(arr, i, arr.length);
        }
        //再依次交换堆顶到有序区的头部，然后调整堆
        for (int i = arr.length - 1; i > 0; i--) {
            T tmp = arr[i];
            arr[i] = arr[0];
            arr[0] = tmp;
            siftDown2(arr, 0, i);
        }
    }

    //第一种下沉操作的写法
    private void siftDown(T[] arr, int index, int n) {
        T key = arr[index]; //保存当前要下沉操作的对象
        int half = (n >>> 1) - 1; //最后一个非叶子结点，超出这个范围就不可能再下沉了
        while (index <= half) {
            //先找到左右子节点中的较大者
            int child = (index << 1) + 1;
            int right = child + 1;
            if (right < n && arr[child].compareTo(arr[right]) < 0) {
                child = right;
            }
            //较大的子节点比父节点还大，则交换
            if (arr[child].compareTo(key) > 0) {
                arr[index] = arr[child];
                index = child;
            } else { //否则，说明已经堆化了，直接退出
                break;
            }
        }
        arr[index] = key;
    }

    //第二种下沉操作的写法，可能更好理解
    private void siftDown2(T arr[], int index, int n) {
        T key = arr[index]; //保存要比较的对象（保存是为了不用每次都交换）
        int childIndex = (index << 1) + 1;
        while (childIndex < n) {
            if (childIndex + 1 < n && arr[childIndex + 1].compareTo(arr[childIndex]) > 0) {
                childIndex++;
            }
            if (arr[childIndex].compareTo(key) > 0) {
                arr[index] = arr[childIndex];
                index = childIndex;
                childIndex = (index << 1) + 1;
            } else {
                break;
            }
        }
        arr[index] = key;
    }
}
